package org.moonshiner.alg.quicksort;

import org.moonshiner.alg.util.StdRandom;

public class Quick3way {

	public static void sort(Comparable[] a) {
		StdRandom.shuffle(a);
		sort(a, 0, a.length - 1);
	}

	private static void sort(Comparable[] a, int low, int high) {
		if (high <= low) {
			return;
		}

		int lt = low, i = low + 1, gt = high;
		Comparable v = a[low];
		
		while(i <= gt){
			int cmp = a[i].compareTo(v);
			if(cmp < 0){
				exch(a, lt++, i++);
			}else if(cmp > 0){
				exch(a, i, gt--);
			}else{
				i++;
			}
		}
		sort(a, low, lt-1);
		sort(a, gt+1, high);
		
	}
	
	private static void exch(Object[] a, int i, int j) {
		Object swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}

}
